//键盘输入n个有序值建立线性表，按折半查找查找给定key的元素
#include<stdio.h>
#include<stdlib.h>
typedef struct SeqList
{
    int* data;
    int length;
}SeqList;



int BinSrch(SeqList* L,int key);
int binarySearch(SeqList L, int key);
int initseqList(SeqList* L,int n);
int insertseqList(SeqList* L,int i,int element);
void freeList(SeqList* L);


int main(){
    int n;
    scanf("%d",&n);
    SeqList L;
    initseqList(&L,n);
    int i=0;
    printf("please input data:\n");
    while (i<n)
    {   
        int input;
        scanf("%d",&input);
        insertseqList(&L,i,input);
        i++;
    }
    printf("please input search key:\n");
    int key;
    scanf("%d",&key);
    int res=BinSrch(&L,key);
    printf("res:%d\n",res);
    freeList(&L);

    return 0;

}

// 折半查找
int binarySearch(SeqList L, int key) {
    int low = 0;
    int high = L.length - 1;
    int mid;
    while (low <= high) {
        mid = (low + high) / 2;
        if (L.data[mid] == key) {
            return mid;
        } else if (L.data[mid] > key) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return -1;
}

int BinSrch(SeqList* L,int key){
    int low=0,hight=L->length-1;
    int mid;
    while(low<=hight){
        mid=(low+hight)/2;
        if (key==L->data[mid]){
            return mid;
        }else if(key<L->data[mid]){
            hight=mid-1;
        }else{
            low=mid+1;
        }
    }
    return -1;
}

int initseqList(SeqList* L,int n){
    L->data=(int*)malloc(n*sizeof(int));
    L->length=0;
    return 0;
}

int insertseqList(SeqList* L,int i,int element){
    L->data[i]=element;
    L->length++;
    return 0;
}

int insertseqList1(SeqList *L, int element){
    int *newData = (int *)realloc(L->data, (L->length + 1) * sizeof(int));
    if (newData!= NULL) {
        newData[L->length] = element;
        L->data = newData;
        L->length++;
    } else {
        printf("内存分配失败！\n");
        return -1;
    }
    return 0;
}

// 释放线性表内存
void freeList(SeqList* L) {
    free(L->data);
    L->data = NULL;
    L->length = 0;
}


